import numpy as np
import csv
import random
from collections import Counter

def load_iris(path: str):
    X, y = [], []
    with open(path, newline='D:\jiqixuexi\iris\bezdekIris.data') as f:
        for row in csv.reader(f):
            if len(row) != 5:
                continue
            X.append([float(v) for v in row[:4]])
            y.append(row[4].strip())
    return np.array(X), np.array(y)

def train_test_split(X, y, test_ratio=0.3, seed=None):
    if seed is not None:
        random.seed(seed)
    classes = list(set(y))
    train_idx, test_idx = [], []
    for c in classes:
        idx = np.where(y == c)[0].tolist()
        random.shuffle(idx)
        n_test = int(len(idx) * test_ratio)
        test_idx.extend(idx[:n_test])
        train_idx.extend(idx[n_test:])
    random.shuffle(train_idx)
    random.shuffle(test_idx)
    return X[train_idx], X[test_idx], y[train_idx], y[test_idx]

def normalize(X_train, X_test):
    xmin = X_train.min(axis=0)
    xmax = X_train.max(axis=0)
    def minmax(X):
        return (X - xmin) / (xmax - xmin)
    return minmax(X_train), minmax(X_test)

def euclidean(a, b):
    return np.sqrt(np.sum((a - b) ** 2))

class KNN:
    def __init__(self, k=3):
        self.k = k

    def fit(self, X, y):
        self.X_train = X
        self.y_train = y

    def _predict_one(self, x):
        dists = [euclidean(x, xtr) for xtr in self.X_train]
        k_idx = np.argsort(dists)[:self.k]
        k_labels = self.y_train[k_idx]
        return Counter(k_labels).most_common(1)[0][0]

    def predict(self, X):
        return np.array([self._predict_one(x) for x in X])

    def score(self, X, y):
        return np.mean(self.predict(X) == y)

def main():
    X, y = load_iris("iris.data")
    X_train, X_test, y_train, y_test = train_test_split(X, y, test_ratio=0.3, seed=42)
    X_train, X_test = normalize(X_train, X_test)

    best_k, best_acc = 1, 0.0
    for k in range(1, 16, 2):          
        clf = KNN(k=k)
        clf.fit(X_train, y_train)
        acc = clf.score(X_test, y_test)
        print(f"k={k:2d}  测试准确率 = {acc:.4f}")
        if acc > best_acc:
            best_acc, best_k = acc, k

    print("\n最佳 k =", best_k, "准确率 =", best_acc)

if __name__ == "__main__":
    main()